#include "stdio.h"
#include "stdlib.h"
#include "string.h"
 
typedef char ElemType;
 
typedef struct Node {
    ElemType data;
    struct Node *next;
}LinkNode;
 
void CreateListR(LinkNode *&L, ElemType a[], int n)
{
    LinkNode *node = NULL;
    int i = 0;
    L = (LinkNode *)malloc(sizeof(LinkNode));
    L->next = NULL;
    
    LinkNode *p = L;
    for(i=0; i<n; i++)
    {
        node = (LinkNode *)malloc(sizeof(LinkNode));
        node->data = a[i];
        node->next = NULL;
        p->next = node;
        p = node;
    }
}
 
void DispList(LinkNode *L)
{
    LinkNode *p = L->next;
    while(p)
    {
        printf("%c ",p->data);
        p = p->next;
    }
    printf("\n");
}
 
void Split(LinkNode *L, ElemType x)
{
   
    LinkNode* pLeftHead = (LinkNode *)malloc(sizeof(LinkNode));
    LinkNode* pRightHead = (LinkNode *)malloc(sizeof(LinkNode));

    LinkNode* left = pLeftHead;
    LinkNode* right = pRightHead;
    LinkNode* p = L->next;
    while(p != NULL)
    {
        if (p->data < x)
        {
            left->next = p;
            left = p;
        }
        else
        {
            right->next = p;
            right = p;
        }
        p = p->next;
    }
    
    
    left->next = pRightHead->next;
    right->next = NULL;
    
    L->next = pLeftHead->next;
    
    free(pLeftHead);
    free(pRightHead);
}
 
void DestroyList(LinkNode* L)
{
    LinkNode* node = L->next;
    while(L != NULL)
    {
        node = L->next;
        free(L);
        L = node;
    }
}
 
int main()
{
    LinkNode *L = NULL;
    ElemType a[] = "fgbedhca";
    int n = strlen(a);
    CreateListR(L, a, n);
    printf("划分前 L: ");
    DispList(L);
    ElemType x = 'd';
    printf("以%c进行划分\n", x);
    Split(L, x);
    printf("划分后 L: ");
    DispList(L);
    DestroyList(L);
    
    return 0;
}
